package middle;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 *
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 * 链接：https://leetcode-cn.com/problems/perfect-squares
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class PerfectSquares {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.numSquares(13);
    }
    /**
     * 21:24 ~ 22:37 1h 13min
     * 时间复杂度仅超过 50%
     * 这种题目 应当考虑是否为动态规划题
     * 该题有点像 丑数 那道题。也有点跟背包问题类似。
     * 1. 定义DP[n]为  n 的完全平方数的最少数量
     * 2. 找出状态转移方程:dp[i] = Min(dp[i], dp[i- j*j] + 1)
     * 对于一个完全平方数来说 其值就是1 所以i-j*j 如果为平方数，则值为0。下标为0的值为0 ，0+1 = 1；
     * 对于不是完全平方数来说，我们就去遍历其在减去各完全平方数后 得到的最小值
     * 3. 初始化值 不用初始化
     * */
    static class Solution {
        public int numSquares(int n) {
            int[] dp = new int[n+1];
            List<Integer> squareNums = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                if(isSquares(i)){
                    dp[i] = 1;
                    squareNums.add(i);
                }else{
                    int min = Integer.MAX_VALUE;
                    for (int squareNum : squareNums){
                        min = Math.min(min, dp[squareNum] + dp[i - squareNum]);
                    }
                    dp[i] = min;
                }
            }
            return dp[n];
        }

        boolean isSquares(int n){
            for (int i = 1; i <= n; i++) {
                if(i * i == n){
                    return true;
                }
            }
            return false;
        }
    }
}
